#include "algorithm.h"
#include <iostream>

/* begin */
// entrance for fibonaci
const int factorial(const int &n, bool is_recursion) {
	//here do not check n > 0
	if (is_recursion) {
		return factorial_recursion(n);
	}
	return factirial_nrecursion(n);
}
// recursion mode
const int factorial_recursion(const int &n) {
	if (0 == n) {
		return 1;
	}
	return factorial_recursion(n - 1) * n;
}
// nonrecursion mode
const int factirial_nrecursion(const int &n) {
	int result = 1, i = 1;
	while (i < n) {
		result *= ++i;
	}
	return result;
}
/* end */

/* being */
// entrance for fibonaci
const int fibonaci(const int &n, bool is_recursion) {
	if (is_recursion) {
		return fibonaci_recursion(n);
	}
	return fibonaci_nrecursion(n);
}
// recursion mode
const int fibonaci_recursion(const int &n) {
	if (n < 2) {
		return 1;
	}
	return fibonaci_recursion(n - 1) * fibonaci_recursion(n - 2);
}
// nonrecursion mode
const int fibonaci_nrecursion(const int &n) {
	double sqrt5 = sqrt(5.0);
	return (int)(1 / sqrt5 * (pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1)));
}
// nonrecursion mode in loop
const int fibonaci_nrecursion_loop(const int &n) {
	int a = 1, b = 1, result = 0, i = 1;
	while (i < n) {
		result = a + b;
		a = b;
		b = result;
		++i;
	}
	return result;
}
/* end */

/* begin */
// nums of integer division using recursion
// @params number target
// @params max	  max number in division
const int integer_division(const int &number, const int &max) {
	if (number < 1 || max < 1) {
		// it seems not necessary this line
		return 0;
	}

	if (1 == number || 1 == max) {
		return 1;
	}

	if (number < max) {
		return integer_division(number, number);
	}

	if (number == max) {
		return integer_division(number, max - 1) + 1;
	}

	return integer_division(number, max - 1) + integer_division(number - max, max);
}
/* end */

/* begin */
// hanoi using recursion
void hanoi(const int &n, const int &src, const int &dest, const int &help) {
	if (n > 0) {
		hanoi(n - 1, src, help, dest);
		move(src, dest);
		hanoi(n - 1, help, dest, src);
	}
}

void move(const int &src, const int &dest) {
	const static char names[] = {'a', 'b', 'c'};
	std::cout << names[src] << "->" << names[dest] << std::endl;
}
/* end */

/* begin */
// longest common sub sequence length
void LCSLength(const char *s1, const char *s2, const int &n1, const int &n2, int **lengths, int **tags) {
	// initialize lengths
	for (int i = 0; i < n1; ++i) lengths[i][0] = 0;
	for (int i = 0; i < n2; ++i) lengths[0][i] = 0;
	if (s1[0] == s2[0])  {
		lengths[0][0] = 1;
		// s1,s2 has the same char in this position
		tags[0][0] = 1;
	}

	for (int i = 1; i < n1; ++i) {
		for (int j = 1; j < n2; ++j) {
			if (s1[i] == s2[j]) {
				lengths[i][j] = lengths[i - 1][j - 1] + 1;
				// s1,s2 has the same char in this position
				tags[i][j] = 1;
			}
			else if (lengths[i - 1][j] > lengths[i][j - 1]){
				lengths[i][j] = lengths[i - 1][j];
				// it should be the result of s1[i-1], s2[j]
				tags[i][j] = 2;
			}
			else {
				lengths[i][j] = lengths[i][j - 1];
				// it should be the result of s1[i], s2[j-1]
				tags[i][j] = 3;
			}
		}
	}
}
/* end */

/* begin */
// find subsequence with the largest sum in an one dimension array
int MSSum(const int list[], const int &left, const int &right) {
	int sum = 0, b = 0;
	for (int i = left; i <= right; ++i) {
		if (b > 0) {
			b += list[i];
		}
		else {
			b = list[i];
		}

		if (b > sum) {
			sum = b;
		}
	}

	return sum;
}

// find subsequence with the largest sum in a two dimension array
int MSSum2(const int * const * list, const int &top, const int &bottom, const int &left, const int &right) {
	const int size = right - left + 1;
	int sum = 0;
	int *b = new int[size];
	for (int i = top; i <= bottom; ++i) {
		for (int j = left; j <= right; ++j) b[j] = 0;

		for (int j = i; j <= bottom; ++j) {
			for (int k = left; k <= right; ++k) {
				b[k] += list[j][k];
			}
			int max = MSSum(b, 0, size - 1);
			if (max > sum) sum = max;
		}
	}
	return sum;
}
/* end */